package leetcode.code1096;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	public List<String> braceExpansionII(String expression) {
		Set<String> set = dfs(expression);
		List<String> ans = new ArrayList<>(set);
		Collections.sort(ans);
		return ans;
	}

	private Set<String> dfs(String expression) {
		Stack<Set<String>> stack = new Stack<>();
		for (int i = 0; i < expression.length();) {
			char c = expression.charAt(i);
			if (c == '{') {// 左括号
				int l = 1, j = i + 1;
				for (; j < expression.length() && l != 0; j++) {
					char k = expression.charAt(j);
					if (k == '{') {
						l++;
					} else if (k == '}') {
						l--;
					}
				}
				Set<String> sub = dfs(expression.substring(i + 1, j - 1));
				if (stack.isEmpty() || stack.peek().contains(",")) {
					stack.add(sub);
				} else {
					Set<String> set = new HashSet<>();
					for (String s : stack.pop()) {
						for (String b : sub) {
							set.add(s + b);
						}
					}
					stack.add(set);
				}
				i = j;
			} else if (c == ',') {// 逗号
				Set<String> set = new HashSet<>();
				set.add(",");
				stack.add(set);
				i++;
			} else {// 字母
				StringBuffer sb = new StringBuffer();
				int j = i;
				while (j < expression.length() && Character.isLetter(expression.charAt(j))) {
					sb.append(expression.charAt(j));
					j++;
				}
				Set<String> sub = new HashSet<>();
				sub.add(sb.toString());
				if (stack.isEmpty() || stack.peek().contains(",")) {
					stack.add(sub);
				} else {
					Set<String> set = new HashSet<>();
					for (String s : stack.pop()) {
						for (String b : sub) {
							set.add(s + b);
						}
					}
					stack.add(set);
				}
				i = j;
			}
		}
		Set<String> ans = new HashSet<>();
		while(!stack.isEmpty()) {
			Set<String> cur = stack.pop();
			if(cur.contains(",")) {
				continue;
			}
			for(String s : cur) {
				ans.add(s);
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
//		H.print(this.braceExpansionII("{a,b}{c,aaa{d,e}}"));
		H.print(this.braceExpansionII("{a,b}{c,{d,e}}"));
//		H.print(this.braceExpansionII("{a{a{c,d,a{d,e}{c,d}a,a{d,e}{c,d}a,{d,e}{c,d}a}},{e,f}}"));
//		H.print(this.braceExpansionII("{a,b}{c,{d,e}}"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
